﻿#include <iostream>
#include <unordered_map>

using namespace std;

static char* delExtraCharacters(const char* text)
{
    auto len = strlen(text);
    if (len == 1)
    {
        char* one = (char*)malloc(2);
        one[0] = text[0];
        one[1] = '\0';
        return one;
    }

    unordered_map<char, int> frequencyTable;
    for (int i = 0; i < len; i++)
    {
        char cur = text[i];
        frequencyTable[cur]++;
    }

    int minCharacterIndex = 0;
    for (int i = 0; i < len; i++)
    {
        char cur = text[i];
        auto f = frequencyTable[cur];
        frequencyTable[cur] = f--;
        minCharacterIndex = text[minCharacterIndex] > cur ? i : minCharacterIndex;
        if (f == 0)
        {
            break;
        }
    }

    char* subStr = (char*)malloc(len - minCharacterIndex);
    memset(subStr, 0, len - minCharacterIndex);
    int index = 0;
    for (int i = minCharacterIndex + 1; i < len; i++)
    {
        char cur = text[i];
        if (cur == text[minCharacterIndex])
            continue;

        subStr[index++] = cur;
    }

    char* nextStr = delExtraCharacters(subStr);
    free(subStr);
    char* res = (char*)malloc(strlen(nextStr) + 2);
    memset(res, 0, strlen(nextStr) + 2);
    index = 0;
    res[index++] = text[minCharacterIndex];
    for (int i = 0; i < strlen(nextStr); i++)
    {
        res[index++] = nextStr[i];
    }

    free(nextStr);
    return res;
}

//  给定一个全是小写字母的字符串str，删除多余字符，使得每种字符只保留一个，并让最终结果字符串的字典序最小
//  举例:
// str = "acbc", 删掉第一个'c', 得到"abc", 是所有结果字符串中字典序最小的。
//  str = "dbcacbca", 删掉第一个'b', 第一个'c', 第二个'c', 第二个'a', 得到"dabc",
//  是所有结果中字典序最小的。
// 
//  思路：
//  贪心，
//  1. 依次统计每个字符的词频，建立词频表。
//  2. 遍历字符串，每过一个字符，词频表中的这个字符的词频数量 - 1，直到找到一个i位置，从i开始，就出现有字符的 词频变成0了。
//  3. 从0->i - 1, 找到ASCII码最小的字符x的位置k，把k之前的字符都删掉，再把k之后的字符x都删掉。
//  4. 对于k之后的子串，将它作为一个单独的字符串，重新开始步骤1...
int main_KeepOnlyOneCharacterToMakeMinLexicographicalOrder()
{
    char text[256] = "zzddjsklcvcvahbz";
    char* res = delExtraCharacters(text);
    printf("%s\n", res);
    free(res);
    return 0;
}